1. Field of the Invention
This invention relates to microprocessors, and more particularly, to branch prediction mechanisms.
2. Description of the Relevant Art
During each clock cycle a microprocessor ideally produces useful execution of an instruction for each stage of a pipeline. However, a stall in a pipeline may prevent useful work from being performed during one or more particular pipeline stages. Some stalls may last several clock cycles and significantly decrease processor performance. An example of a stall is a mispredicted branch instruction.
Techniques for reducing the negative effect of stalls include overlapping pipeline stages, allowing out-of-order execution of instructions, and supporting simultaneous multi-threading. However, a stall of several clock cycles still reduces the performance of the processor due to in-order retirement that may prevent hiding of all the stall cycles. To prevent this performance loss, techniques for reducing the occurrence of the multi-cycle stalls may be used. One example of such a technique is branch prediction.
Branch prediction techniques predict an evaluation of a condition of a branch instruction. In addition, branch prediction techniques may predict a branch target address. The branch prediction logic may be complex in order to provide a high accuracy. Therefore, the branch prediction logic may use multiple clock cycles to perform evaluations and calculations to produce results for the condition and the branch target address. However, during these multiple clock cycles, instructions are being fetched from the instruction cache. These fetched instructions may be flushed if the branch prediction logic determines other instructions should be fetched.
The branch prediction logic may utilize logic that trades off accuracy for faster results. However, the lower accuracy may lead to situations where a small, repeating loop branch with a varying branch pattern is not evaluated properly. This case leads to mispredictions a large majority of the time and constantly flushed instruction in a corresponding pipeline.
In view of the above, efficient methods and mechanisms for efficient branch prediction are desired.